package LeetCode75;

import publicClass.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 872. 叶子相似的树
 * 请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
 *
 *
 *
 * 举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
 *
 * 如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
 *
 * 如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
 * 输出：true
 * 示例 2：
 *
 *
 *
 * 输入：root1 = [1,2,3], root2 = [1,3,2]
 * 输出：false
 *
 *
 * 提示：
 *
 * 给定的两棵树结点数在 [1, 200] 范围内
 * 给定的两棵树上的值在 [0, 200] 范围内
 */
public class T0872_叶子相似的树 {


    //深度优先遍历 使用递归完成 先找左边的子叶 再找右边的子叶
    public static boolean leafSimilar(TreeNode root1, TreeNode root2) {
        //存放 两颗数 的子叶
        ArrayList<Integer> r1 = new ArrayList<>();
        ArrayList<Integer> r2 = new ArrayList<>();

        dfs(root1,r1);
        dfs(root2,r2);

        if (r1.size()!=r2.size()){
            return false;
        }

        for (int i = 0; i < r1.size(); i++) {
            if (r1.get(i) != r2.get(i)){
                return false;
            }
        }
        return true;
    }

    public static void dfs(TreeNode root,List<Integer> list){

        if (root==null){
            return;
        }

        if (root.left==null&&root.right==null){
            //这是一个子叶
            list.add(root.val);
        }

        //按照循序 从左到右
        dfs(root.left,list);
        dfs(root.right,list);

    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        treeNode1.left = treeNode2;

        TreeNode treeNode22 = new TreeNode(2);
        treeNode22.left = new TreeNode(2);
        leafSimilar(treeNode1,treeNode22);

    }

}
